package cn.bellychang.leetcode.question033;

/**
 * You are given an integer array nums sorted in ascending order (with distinct values), and an integer target.
 * <p>
 * Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
 * <p>
 * If target is found in the array return its index, otherwise, return -1.
 * <p>
 * Constraints:
 * nums is guaranteed to be rotated at some pivot.
 *
 * 看起来只能有一个pivot
 *
 * @author ChangLiang
 * @date 2021/2/4
 */
public class Solution {

    public int search(int[] nums, int target) {
        return search(0, nums.length-1, nums, target);
    }

    private int search(int beginIndex, int endIndex, int[] nums, int target) {
        int pivotIndex = findPivot(beginIndex, endIndex, nums);

        if (pivotIndex == -1) {
            int i = binarySearch(beginIndex, endIndex, nums, target);
            return i;
        } else {
            int j = search(beginIndex, pivotIndex, nums, target);
            if (j != -1) {
                return j;
            }
            int k = search(pivotIndex + 1, endIndex, nums, target);
            if (k != -1) {
                return k;
            }
        }
        return -1;
    }

    private int binarySearch(int beginIndex, int endIndex, int[] nums, int target) {
        int l = beginIndex;
        int r = endIndex;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public int findPivot(int beginIndex, int endIndex, int[] nums) {
        if (beginIndex == endIndex) {
            return -1;
        }
        if (nums[beginIndex] > nums[beginIndex + 1]) {
            return 0;
        }

        int temp = beginIndex;
        // loop invariant: [beginIndex..temp]是顺序的
        for (int i = beginIndex + 1; i <= endIndex; i++) {
            if (nums[temp] > nums[i]) {
                return i - 1;
            }
            temp++;
        }
        return -1;
    }
}
